package com.ljy.my_study.lintcode.K数之和;

import java.util.LinkedList;
import java.util.Queue;

/** 
* @author James
* @date 2018年9月30日 
*/
public class TestMain2 {
//	描述
//	给定 n 个不同的正整数，整数 k（k <= n）以及一个目标数字 target。　
//	在这 n 个数里面找出 k 个数，使得这 k 个数的和等于目标数字，求问有多少种方案？
//
//	您在真实的面试中是否遇到过这个题？  
//	样例
//	给出 [1,2,3,4]，k=2， target=5，[1,4] 和 [2,3] 是 2 个符合要求的方案，返回 2。
	public static void main(String[] args) {
		int[] nums= {1,3,4,5,6,8,11,14,16,19,20,23,25,28,30,33,34,36,39,41,43,45,46,48,51,53,55,56,58,59,60};
		System.out.println(kSum(nums,26,811));
//		int[] nums= {1,2,4,5,7,8,10,11,12,13,15};
//		System.out.println(kSum(nums,3,16));
//		int[] nums= {1,4,7,9,10,12,15,18,20,21,22,25,28,31,33,36,38,39,41,43,44,45,48,50,53};
//		System.out.println(kSum(nums,21,617));
//		int[] nums= {1,2,3,4,5,6,7};
//		System.out.println(kSum(nums,4,12));
	}
	
	public static int kSum(int[] A, int k, int target) {
		int n=0;
		int index=0;
		if(k==1) {
			for(int i=0;i<A.length;i++) {
				if(A[i]==target) {
					n++;
				}
			}
			return n;
		}
		while(index<A.length-k) {
			n+=kSum(A,k,target,index+1,A[index],1);
			index++;
		}
		return n;
	}
	
	public static int kSum(int[] A,int k,int target,int index,int sum,int count) {
		int n=0;
		if(index>A.length) {
			return 0;
		}
		if(count>k||sum>target) {
			return 0;
		}
		if(sum==target&&count==k) {
			return 1;
		}
		for(int i=index;i<A.length;i++) {
			if(count>k||sum>target) {
				break;
			}else if(sum<target) {
				n+=kSum(A,k,target,i+1,sum+A[i],count+1);
			}
		}
		return n;
	}
}
